package com.uraurora.crescent.advanced.tree.impl;

import com.uraurora.crescent.advanced.tree.AbstractSegmentTree;
import com.uraurora.crescent.advanced.tree.ISegmentTree;
import com.uraurora.crescent.advanced.tree.ITreeNodeMerger;

import java.util.Iterator;
@Deprecated
public class LinkedSegmentTree<T> extends AbstractSegmentTree<T> implements ISegmentTree<T> {

    private int size;

    private int dataSize;

    private T[] data;

    private ITreeNodeMerger<T> merger;

    private static class SegmentTreeNode<T>{
        int start;
        int end;
        T val;

        SegmentTreeNode<T> leftNode = null;
        SegmentTreeNode<T> rightNode = null;

        public SegmentTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    @Override
    public boolean update(int index, T value) {
        return false;
    }

    @Override
    public boolean update(int left, int right, T value) {
        return false;
    }

    @Override
    public T query(int index, T initValue) {
        return null;
    }

    @Override
    public T query(int left, int right, T initValue) {
        return null;
    }

    public boolean set(int index, T value) {
        return false;
    }

    @Override
    public Iterator<T> iterator() {
        return null;
    }

    @Override
    public int size() {
        return 0;
    }

    //<editor-fold desc="Private Methods">

    private void buildTree(T[] arr, SegmentTreeNode<T> root, int start, int end){
        if (start == end) {
            root.val = arr[start];
        }
        else {
            int mid = start + end >> 1;
            root.leftNode = new SegmentTreeNode<>(start, mid);
            root.rightNode = new SegmentTreeNode<>(mid+1, end);

            buildTree(arr, root.leftNode, start, mid);
            buildTree(arr, root.rightNode, mid + 1, end);
            root.val = merger.updateMerge(root.leftNode.val, root.rightNode.val);
        }
    }

    private void internalUpdate(T[] arr, SegmentTreeNode<T> root, int start, int end, int index, T val){
        if (start == end) {
            arr[index] = merger.updateMerge(data[index], val);
            root.val = merger.updateMerge(root.val, val);
        }
        else {
            int mid = start + end >> 1;
            if (index >= start && index <= mid) {
                internalUpdate(arr, root.leftNode, start, mid, index, val);
            }
            else{
                internalUpdate(arr, root.rightNode, mid+1, end, index, val);
            }
            root.val = merger.updateMerge(root.leftNode.val, root.rightNode.val);
        }
    }

    private T internalQuery(T[] arr, SegmentTreeNode<T> root, int start, int end, int left, int right, T initValue){
        if (right < start || left > end) {
            return initValue;
        }
        else if(start == end){

            return root.val;
        }
        else if(left <= start && right >= end){
            return root.val;
        }
        else {
            int mid = start + end >> 1;

            T resLeft = internalQuery(arr, root.leftNode, start, mid, left, right, initValue);
            T resRight = internalQuery(arr, root.rightNode, mid+1, end, left, right, initValue);
            return merger.updateMerge(resLeft, resRight);
        }
    }

    /**
     * 计算完全二叉树的节点树，并非是真正的节点个数，因为完全二叉树形式的实现，会导致
     * 叶子节点有很多无用的节点
     * @param n 区间范围的元素个数
     * @return 计算的完全二叉树所有的节点数
     */
    private int calculateTreeSize(int n){
        return (int) (Math.pow(2, Math.ceil(log(2, n) + 1)) - 1);
    }

    public static double log(double base, double value) {
        return Math.log(value) / Math.log(base);
    }
    //</editor-fold>
}
